package primary.code05_Tree;

import java.util.Stack;

/**
 * @author Yudi Wang
 * @date 2021/7/9 16:51
 * <p>
 * 判断是否为搜索二叉树
 * 1 中序遍历，遍历的节点均处于上升的趋势
 * 2 树DP，左右子树为搜索树，并且与根节点构成搜索树来判断
 */
public class Code04_BinarySearchTree {

    private static int preValue = Integer.MIN_VALUE;//类变量

    /**
     * 循环 中序遍历
     * 遍历的节点均处于上升的趋势
     *
     * @param head
     * @return
     */
    private static boolean judgeSBT1(Node head) {
        if (head == null) return true;
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        int preDate = Integer.MIN_VALUE;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            //遍历处理
            if (preDate > cur.data) return false;
            preDate = cur.data;
            cur = cur.right;
        }
        return true;
    }

    static class NodeFlag {
        Node node;
        int flag;

        public NodeFlag(Node node, int flag) {
            this.node = node;
            this.flag = flag;
        }
    }

    private static boolean judgeSBT1Test(Node root) {
        if (root == null) {
            return true;
        }
        int pre = Integer.MIN_VALUE;
        Stack<NodeFlag> stack = new Stack<>();
        stack.push(new NodeFlag(root, 1));
        while (!stack.isEmpty()) {
            NodeFlag cur = stack.pop();
            if (cur.flag == 1) {
                if (cur.node.right != null) {
                    stack.push(new NodeFlag(cur.node.right, 1));
                }
                stack.push(new NodeFlag(cur.node, 2));
                if (cur.node.left != null) {
                    stack.push(new NodeFlag(cur.node.left, 1));
                }
            } else {
                if (cur.node.data < pre) {
                    return false;
                }
                pre = cur.node.data;
            }
        }
        return true;
    }

    private static Node preNode = null;

    /**
     * 递归 中序遍历
     * 遍历的节点均处于上升的趋势
     *
     * @param head
     * @return
     */
    private static boolean judgeSBT2(Node head) {
        if (head == null) return true;
        if (judgeSBT2(head.left) == false) return false;
        //遍历到当前树节点，存在null的情况
        if (preValue > head.data) return false;
        preValue = head.data;
        if (judgeSBT2(head.right) == false) return false;
        return true;
    }

    private static boolean judgeSBT2Test(Node head) {
        if (head == null) {
            return true;
        }
        boolean left = judgeSBT2Test(head.left);
        if (left == false) {
            return false;
        }
        if (preNode != null && preNode.data > head.data) {
            return false;
        }
        preNode = head;
        boolean right = judgeSBT2Test(head.right);
        return right;
    }

    /**
     * 树 DP
     * 左右子树为搜索树，并且与根节点构成搜索树来判断
     *
     * @param head
     * @return
     */
    private static ReturnDate judgeSBT3(Node head) {
        if (head == null) return new ReturnDate(null, null, true);
        ReturnDate left = judgeSBT3(head.left);
        ReturnDate right = judgeSBT3(head.right);
        if (left.isBST && right.isBST
                && (left.max != null ? left.max <= head.data : true)
                && (right.min != null ? right.min >= head.data : true)) {
            return new ReturnDate(left.min != null ? left.min : head.data,
                    right.max != null ? right.max : head.data, true);
        }
        return new ReturnDate(null, null, false);
    }

    private static ReturnDate judgeSBT3Test0(Node head) {
        if (head == null) {
            return new ReturnDate(null, null, true);
        }
        ReturnDate lrd = judgeSBT3Test0(head.left);
        ReturnDate rrd = judgeSBT3Test0(head.right);
        boolean isBST = false;
        if (
                lrd.isBST && rrd.isBST
                        && (lrd.max == null || lrd.max <= head.data)
                        && (rrd.min == null || rrd.min >= head.data)
        ) {
            isBST = true;
        }
        return new ReturnDate(lrd.min == null ? head.data : lrd.min, rrd.max == null ? head.data : rrd.max, isBST);
    }

    private static boolean judgeSBT3Test(Node head) {
        ReturnDate returnDate = judgeSBT3Test0(head);
        return returnDate.isBST;
    }

    public static void main(String[] args) {
        Node head = new Node(4);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.left.left.left = new Node(1);
        head.right.left = new Node(7);
        head.right.left.left = new Node(6);
        head.right.right = new Node(10);
        head.right.right.left = new Node(9);
        head.right.right.right = new Node(11);
//        head.right.right.right.right = new Node(3);
        System.out.println(judgeSBT1(head));
        System.out.println(judgeSBT1Test(head));
        System.out.println(judgeSBT2(head));
        System.out.println(judgeSBT2Test(head));
        System.out.println(judgeSBT3(head).isBST);
        System.out.println(judgeSBT3Test(head));
    }

    public static class ReturnDate {
        private Integer min;
        private Integer max;
        private boolean isBST;

        public ReturnDate(Integer min, Integer max, boolean isBST) {
            this.min = min;
            this.max = max;
            this.isBST = isBST;
        }
    }
}
